package com.jzoffer;

/*
* 地上有一个m行和n列的方格。
* 一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
* 但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），
* 因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
* 请问该机器人能够达到多少个格子
*
* */

public class TheRangeOfRobotSport {
    public static void main(String[] args) {
        int i = movingCount(7, 4, 8);
        System.out.println(i);

    }

    public static int movingCount(int threshold, int rows, int cols){
        if(rows < 1 || cols < 1){
            return 0;
        }
        int [][] hasWalkedMatrix = new int[rows][cols];
        int [][] directions = {{-1,0},{1,0},{0,-1,0,1}};
        int count = subMovingCount(hasWalkedMatrix,rows,cols,directions,threshold,0,0);
        return count;
    }

    private static int subMovingCount(int[][] hasWalkedMatrix,int rows,int cols,int [][]directions,int threshold,int i ,int j ){
        if(i < 0 || i >= rows || j < 0 || j >= cols || hasWalkedMatrix[i][j] == 1 || isBiggerThanK(i,j,threshold)){
            return 0;
        }
        int sum = 1;
        hasWalkedMatrix[i][j] = 1;
        for(int k = 0; k < directions.length;k++){
            int r = i + directions[k][0];
            int c = j + directions[k][1];
            sum += subMovingCount(hasWalkedMatrix,rows,cols,directions,threshold,r,c);
        }
        return sum;
    }

    private static boolean isBiggerThanK(int i,int j,int threshold){
        int sum = 0;
        while (i != 0){
            sum += i % 10;
            i /= 10;
        }
        while (j != 0){
            sum += j% 10;
            j /= 10;
        }
        return sum > threshold;
    }
}
